package com.mjx.algorithm;

/**
 * 归并排序：最小从两个大小为1的数组合并，逐渐扩大。
 * 效率O(N*logN)
 * Created by meijingxiang on 2017/2/3.
 */
public class MergeSort {
    private static int[] inputArray;

    public static int[] mergeSort(int[] array) {
        inputArray = array;
        realSort(0, array.length-1);
        return inputArray;
    }

    //递归调用排序
    private static void realSort(int low, int upper){
        if (low == upper)
            return;
        int mid = (low + upper) / 2;
        realSort(low, mid);
        realSort(mid + 1, upper);
        merge(low, mid + 1, upper);
    }

    //合并两个有序的数组
    private static void merge(int low, int mid, int upper) {
        int index = 0;
        int lowIndex = low, midIndex = mid;
        int n = upper - low + 1;
        int []array = new int[n];
        while (lowIndex <= mid - 1 && midIndex <= upper) {//low->mid-1相当于第一个数组，mid->upper是第二个数组
            if (inputArray[lowIndex] < inputArray[midIndex]) {
                array[index++] = inputArray[lowIndex++];
            } else {
                array[index++] = inputArray[midIndex++];
            }
        }
        //第一个数组比第二个长的情况
        while (lowIndex <= mid - 1) {
            array[index++] = inputArray[lowIndex++];
        }
        //第二个数组比第一个长的情况
        while (midIndex <= upper) {
            array[index++] = inputArray[midIndex++];
        }
        //打印排序过程
        show(n,array,low);
        //将排好的顺序放回原数组
        for (int i = 0; i < n; i++) {
            inputArray[low + i] = array[i];
        }
    }

    private static void show(int n,int[] array,int low){
        System.out.println("排序前");
        for (int i = 0; i < n; i++)
            System.out.print(inputArray[low + i]+" ");
        System.out.println();
        System.out.println("排序后");
        for (int i = 0; i < n; i++) {
            System.out.print(array[i]+" ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int []array={3,2,1,7,6,5};
        mergeSort(array);
        for (int i = 0; i < array.length; i++) {
            System.out.println(array[i]);
        }
    }
}
